SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Complementary sequences</title>

</head>

Complementary sequences

</h1>

</header>

<dl><dd>For complementary sequences in biology, see <a href="Complementarity_(molecular_biology)" title="Complementarity (molecular biology)">complementarity (molecular biology)</a>. For integer sequences with complementary sets of members see <a href="Lambek%E2%80%93Moser_theorem" title="Lambek–Moser theorem">Lambek–Moser theorem</a>.</dd></dl>

In applied mathematics, complementary sequences (CS) are pairs of <a href="Sequence" title="Sequence">sequences</a> with the useful property that their out-of-phase aperiodic <a href="Autocorrelation" title="Autocorrelation">autocorrelation</a> coefficients sum to zero. Binary complementary sequences were first introduced by <a href="Marcel_J._E._Golay" title="Marcel J. E. Golay">Marcel J. E. Golay</a> in 1949. In 1961–1962 Golay gave several methods for constructing sequences of length 2N and gave examples of complementary sequences of lengths 10 and 26. In 1974 R. J. Turyn gave a method for constructing sequences of length mn from sequences of lengths m and n which allows the construction of sequences of any length of the form 2N10K26M.

Later the theory of complementary sequences was generalized by other authors to polyphase complementary sequences, multilevel complementary sequences, and arbitrary complex complementary sequences. Complementary sets have also been considered; these can contain more than two sequences.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Let (a0, a1, ..., aN − 1) and (b0, b1, ..., bN − 1) be a pair of bipolar sequences, meaning that a(k) and b(k) have values +1 or −1. Let the aperiodic <a href="Autocorrelation_function" class="mw-redirect" title="Autocorrelation function">autocorrelation function</a> of the sequence x be defined by

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{x}(k)=\sum _{j=0}^{N-k-1}x_{j}x_{j+k}.\,}</annotation>

</semantics>

</math><img src="./85f070c1e4e082707a686e3483ca5baccf7ea1e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:22.785ex; height:7.676ex;" alt="{\displaystyle R_{x}(k)=\sum _{j=0}^{N-k-1}x_{j}x_{j+k}.\,}" loading="lazy"></dd></dl>

Then the pair of sequences a and b is complementary if:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{a}(k)+R_{b}(k)=2N,\,}</annotation>

</semantics>

</math><img src="./0e4ed0f0226aa7b8c3afd310f689ce1e418cddaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.807ex; height:2.843ex;" alt="{\displaystyle R_{a}(k)+R_{b}(k)=2N,\,}" loading="lazy"></dd></dl>

for k = 0, and

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{a}(k)+R_{b}(k)=0,\,}</annotation>

</semantics>

</math><img src="./d602994c74d11dece7920cba24554b00b2ef9b44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.744ex; height:2.843ex;" alt="{\displaystyle R_{a}(k)+R_{b}(k)=0,\,}" loading="lazy"></dd></dl>

for k = 1, ..., N − 1.

Or using <a href="Kronecker_delta" title="Kronecker delta">Kronecker delta</a> we can write:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{a}(k)+R_{b}(k)=2N\delta (k),\,}</annotation>

</semantics>

</math><img src="./a14c4fe7cced23f0507ae1dfaed989a8cb028041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.877ex; height:2.843ex;" alt="{\displaystyle R_{a}(k)+R_{b}(k)=2N\delta (k),\,}" loading="lazy"></dd></dl>

So we can say that the sum of autocorrelation functions of complementary sequences is a delta function, which is an ideal autocorrelation for many applications like <a href="Radar" title="Radar">radar</a> <a href="Pulse_compression" title="Pulse compression">pulse compression</a> and <a href="Spread_spectrum" title="Spread spectrum">spread spectrum</a> <a href="Telecommunications" title="Telecommunications">telecommunications</a>.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<ul><li>As the simplest example we have sequences of length 2: (+1, +1) and (+1, −1). Their autocorrelation functions are (2, 1) and (2, −1), which add up to (4, 0).</li>

<li>As the next example (sequences of length 4), we have (+1, +1, +1, −1) and (+1, +1, −1, +1). Their autocorrelation functions are (4, 1, 0, −1) and (4, −1, 0, 1), which add up to (8, 0, 0, 0).</li>

<li>One example of length 8 is (+1, +1, +1, −1, +1, +1, −1, +1) and (+1, +1, +1, −1, −1, −1, +1, −1). Their autocorrelation functions are (8, −1, 0, 3, 0, 1, 0, 1) and (8, 1, 0, −3, 0, −1, 0, −1).</li>

<li>An example of length 10 given by Golay is (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) and (+1, +1, −1, +1, +1, +1, +1, +1, −1, −1). Their autocorrelation functions are (10, −3, 0, −1, 0, 1,−2, −1, 2, 1) and (10, 3, 0, 1, 0, −1, 2, 1, −2, −1).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Properties_of_complementary_pairs_of_sequences">Properties of complementary pairs of sequences</h2></div>

<ul><li>Complementary <a href="Sequences" class="mw-redirect" title="Sequences">sequences</a> have complementary spectra. As the autocorrelation function and the power spectra form a Fourier pair, complementary sequences also have complementary spectra. But as the Fourier transform of a delta function is a constant, we can write</li></ul>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{a}+S_{b}=C_{S},}</annotation>

</semantics>

</math><img src="./200bae1684e599eff8b6568b78e8b1676459a25f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.429ex; height:2.509ex;" alt="{\displaystyle S_{a}+S_{b}=C_{S},}" loading="lazy"></dd></dl></dd></dl>

<dl><dd>where CS is a constant.</dd></dl>

<dl><dd>Sa and Sb are defined as a squared magnitude of the <a href="Fourier_transform" title="Fourier transform">Fourier transform</a> of the sequences. The Fourier transform can be a direct DFT of the sequences, it can be a DFT of zero padded sequences or it can be a continuous Fourier transform of the sequences which is equivalent to the <a href="Z_transform" class="mw-redirect" title="Z transform">Z transform</a> for Z = ejω.</dd></dl>

<ul><li>CS spectra is upper bounded. As Sa and Sb are non-negative values we can write</li></ul>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{a}=C_{S}-S_{b}<C_{S},}</annotation>

</semantics>

</math><img src="./c48c71ab0390a0ffc94f7163a5db67e0670bfea0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.482ex; height:2.509ex;" alt="{\displaystyle S_{a}=C_{S}-S_{b}<C_{S},}" loading="lazy"></dd></dl></dd></dl>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{b}<C_{S}.}</annotation>

</semantics>

</math><img src="./47bf0b9c087e79cce06e4038ba58f7b507f94cdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.062ex; height:2.509ex;" alt="{\displaystyle S_{b}<C_{S}.}" loading="lazy"></dd></dl></dd></dl>

<ul><li>If either of the sequences of the CS pair is inverted (multiplied by −1) they remain complementary. More generally if any of the sequences is multiplied by ejφ they remain complementary;</li>

<li>If either of the sequences is reversed they remain complementary;</li>

<li>If either of the sequences is delayed they remain complementary;</li>

<li>If the sequences are interchanged they remain complementary;</li>

<li>If both sequences are multiplied by the same constant (real or complex) they remain complementary;</li>

<li>If alternating bits of both sequences are inverted they remain complementary. In general for arbitrary complex sequences if both sequences are multiplied by ejπkn/N (where k is a constant and n is the time index) they remain complementary;</li>

<li>A new pair of complementary sequences can be formed as [a b] and [a −b] where [..] denotes concatenation and a and b are a pair of CS;</li>

<li>A new pair of sequences can be formed as {a b} and {a −b} where {..} denotes <a href="Interleave_sequence" title="Interleave sequence">interleaving</a> of sequences.</li>

<li>A new pair of sequences can be formed as a + b and a − b.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Golay_pair">Golay pair</h2></div>

A complementary pair a, b may be encoded as polynomials A(z) = a(0) + a(1)z + ... + a(N − 1)zN−1 and similarly for B(z). The complementarity property of the sequences is equivalent to the condition

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert A(z)\vert ^{2}+\vert B(z)\vert ^{2}=2N\,}</annotation>

</semantics>

</math><img src="./0c37dc2bd3e6c69c0f2eb91d766103417d73f805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.55ex; height:3.176ex;" alt="{\displaystyle \vert A(z)\vert ^{2}+\vert B(z)\vert ^{2}=2N\,}" loading="lazy"></dd></dl>

for all z on the unit circle, that is, |z| = 1. If so, A and B form a Golay pair of polynomials. Examples include the <a href="Shapiro_polynomials" title="Shapiro polynomials">Shapiro polynomials</a>, which give rise to complementary sequences of length a <a href="Power_of_two" title="Power of two">power of two</a>.

<div class="mw-heading mw-heading2"><h2 id="Applications_of_complementary_sequences">Applications of complementary sequences</h2></div>

<ul><li>Multislit spectrometry</li>

<li>Ultrasound measurements</li>

<li>Acoustic measurements</li>

<li><a href="Radar" title="Radar">radar</a> <a href="Pulse_compression" title="Pulse compression">pulse compression</a></li>

<li><a href="Wi-Fi" title="Wi-Fi">Wi-Fi</a> networks,</li>

<li><a href="3G" title="3G">3G</a> <a href="CDMA" class="mw-redirect" title="CDMA">CDMA</a> wireless networks</li>

<li><a href="OFDM" class="mw-redirect" title="OFDM">OFDM</a> communication systems</li>

<li>Train wheel detection systems<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a></li>

<li>Non-destructive tests (NDT)</li>

<li>Communications</li>

<li><a href="Coded_aperture" title="Coded aperture">coded aperture</a> masks are designed using a 2-dimensional generalization of complementary sequences.</li></ul>

<ul><li><a href="Binary_Golay_code" title="Binary Golay code">Binary Golay code</a> (<a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">Error-correcting code</a>)</li>

<li><a href="Gold_code" title="Gold code">Gold sequences</a></li>

<li><a href="Kasami_code" title="Kasami code">Kasami sequences</a></li>

<li><a href="Polyphase_sequence" title="Polyphase sequence">Polyphase sequence</a></li>

<li><a href="Pseudorandom_binary_sequence" title="Pseudorandom binary sequence">Pseudorandom binary sequences</a> (also called <a href="Maximum_length_sequence" title="Maximum length sequence">maximum length sequences</a> or M-sequences)</li>

<li><a href="Ternary_Golay_code" title="Ternary Golay code">Ternary Golay code</a> (<a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">Error-correcting code</a>)</li>

<li><a href="Hadamard_code" title="Hadamard code">Walsh-Hadamard sequences</a></li>

<li><a href="Zadoff%E2%80%93Chu_sequence" title="Zadoff–Chu sequence">Zadoff–Chu sequence</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

Donato, P.G.; Ureña, J.; Mazo, M.; Alvarez, F.

"Train wheel detection without electronic equipment near the rail line".

2004.

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FIVS.2004.1336500">10.1109/IVS.2004.1336500</a>

</li>

J.J. Garcia; A. Hernandez; J. Ureña; J.C. Garcia; M. Mazo; J.L. Lazaro; M.C. Perez; F. Alvarez.

<a rel="nofollow" class="external text" href="http://geintra-uah.org/system/files/private/IV04_I.pdf">"Low cost obstacle detection for smart railway infrastructures"</a>.

2004.

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFGolay1949" class="citation journal cs1"><a href="Marcel_J._E._Golay" title="Marcel J. E. Golay">Golay, Marcel J.E.</a> (1949). "Multislit spectroscopy". J. Opt. Soc. Am. 39 (6): 437–444. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1364%2FJOSA.39.000437">10.1364/JOSA.39.000437</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/18152021">18152021</a>.</cite></li>

<li><cite id="CITEREFGolay1961" class="citation journal cs1">Golay, Marcel J.E. (April 1961). "Complementary series". IRE Trans. Inf. Theory. 7 (2): 82–87. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1961.1057620">10.1109/TIT.1961.1057620</a>.</cite></li>

<li><cite id="CITEREFGolay1962" class="citation journal cs1">Golay, Marcel J.E. (1962). "Note on "Complementary series"". <a href="Proc._IRE" class="mw-redirect" title="Proc. IRE">Proc. IRE</a>. 50: 84. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJRPROC.1962.288278">10.1109/JRPROC.1962.288278</a>.</cite></li>

<li><cite id="CITEREFTuryn1974" class="citation journal cs1">Turyn, R.J. (1974). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2874%2990056-9">"Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings"</a>. J. Comb. Theory A. 16 (3): 313–333. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2874%2990056-9">10.1016/0097-3165(74)90056-9</a>.</cite></li>

<li><cite id="CITEREFBorwein2002" class="citation book cs1"><a href="Peter_Borwein" title="Peter Borwein">Borwein, Peter</a> (2002). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=A_ITwN13J6YC&pg=PA110">Computational Excursions in Analysis and Number Theory</a>. Springer. pp. 110–9. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-95444-8</bdi>.</cite></li>

<li><cite id="CITEREFDonatoUreñaMazoDe_Marziani2006" class="citation journal cs1">Donato, P.G.; Ureña, J.; Mazo, M.; De Marziani, C.; Ochoa, A. (2006). "Design and signal processing of a magnetic sensor array for train wheel detection". Sensors and Actuators A: Physical. 132 (2): 516–525. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2006SeAcA.132..516D">2006SeAcA.132..516D</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.sna.2006.02.043">10.1016/j.sna.2006.02.043</a>.</cite></li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-10-29" href="https://en.wikipedia.org/wiki/?title=Complementary_sequences&oldid=1254065717">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>